package leetcode.D500.T460;

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-14 16:49:16 星期一
 */

class LFUCache {

    private Map<Integer, Integer> KV = new HashMap<>();
    private Map<Integer, Integer> KF = new HashMap<>();
    private Map<Integer, LinkedHashSet<Integer>> FKs = new HashMap<>();
    private int capacity;
    private int minFreq = 0;

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!KV.containsKey(key))
            return -1;
        increaseFrequency(key);
        return KV.get(key);
    }

    public void put(int key, int value) {
        if (!KV.containsKey(key)) {
            if (KV.size() == capacity)
                removeLeastFrequent();
            if (KV.size() >= capacity)
                return;
            KV.put(key, value);
            minFreq = 1;
            KF.put(key, 1);
            if (!FKs.containsKey(1))
                FKs.put(1, new LinkedHashSet<>());
            FKs.get(1).add(key);
        } else {
            KV.put(key, value);
            increaseFrequency(key);
        }
    }

    private void removeLeastFrequent() {
        LinkedHashSet<Integer> keys = FKs.get(minFreq);
        if (keys == null)
            return;
        int key = keys.iterator().next();
        keys.remove(key);
        if (keys.isEmpty())
            FKs.remove(minFreq);
        KV.remove(key);
        KF.remove(key);
    }

    private void increaseFrequency(int key) {
        int freq = KF.get(key);
        if (freq == minFreq && FKs.get(minFreq).size() == 1)
            minFreq++;
        KF.put(key, freq+1);
        LinkedHashSet<Integer> keys = FKs.get(freq);
        keys.remove(key);
        if (keys.size() == 0)
            FKs.remove(freq);
        LinkedHashSet<Integer> newKeys = FKs.getOrDefault(freq+1, new LinkedHashSet<>());
        newKeys.add(key);
        FKs.put(freq+1, newKeys);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */